package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N二叉树展开为链表114.java
 * @Description TODO https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
 * @createTime 2021年04月02日 12:54:00
 */
public class N二叉树展开为链表114 {



    /**
     * todo 前序遍历的方式 空间和时间复杂度都是O(n)
     */
    List<TreeNode> list=new ArrayList<>();
    public void flatten(TreeNode root) {
        beforeTraverse(root);
        for (int i = 1; i < list.size(); i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }

    }

    private void beforeTraverse(TreeNode root) {
        if (root==null){
            return;
        }
        list.add(root);
        beforeTraverse(root.left);
        beforeTraverse(root.right);
    }

    /**
     * 将原来的右子树接到左子树的最右边节点
     * 将左子树插入到右子树的地方
     * 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
     *
     *     1
     *    / \
     *   2   5
     *  / \   \
     * 3   4   6
     *
     * //将 1 的左子树插入到右子树的地方
     *     1
     *      \
     *       2         5
     *      / \         \
     *     3   4         6
     * //将原来的右子树接到左子树的最右边节点
     *     1
     *      \
     *       2
     *      / \
     *     3   4
     *          \
     *           5
     *            \
     *             6
     *
     *  //将 2 的左子树插入到右子树的地方
     *     1
     *      \
     *       2
     *        \
     *         3       4
     *                  \
     *                   5
     *                    \
     *                     6
     *
     *  //将原来的右子树接到左子树的最右边节点
     *     1
     *      \
     *       2
     *        \
     *         3
     *          \
     *           4
     *            \
     *             5
     *              \
     *               6
     *
     *   ......
     *
     * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/
     */
    TreeNode temp=new TreeNode();
    public void flatten2(TreeNode root) {
        while (root!=null){
            //左子树为 null，直接考虑下一个节点
            if (root.left==null){
                root=root.right;
            }else {
                // 找右子树最右边的节点,然后把右子树拼接在后面
                TreeNode temp=root.right;
                while (temp!=null){
                    temp=temp.right;
                }
                //将原来的右子树接到左子树的最右边节点
                temp.right=root.right;
                // 将左子树插入到右子树的地方
                root.right = root.left;
                root.left = null;
                // 考虑下一个节点
                root = root.right;
            }
        }
    }


}
